

public class Main {



    public static class MyCache
    public static class DoubleList{
        Node head;
        Node tail;

        public void addToTail(Node cur) {
            if (head == null) {
                head = tail = cur;
            }else {
                cur.next = tail;
                tail = cur;
            }
        }

        public void moveToHead(Node cur) {
            if (cur == head) {
            return;
            }else
            if (cur == tail) {
                tail = cur.next;
                tail.last = null;
                head.next =cur;
                cur.last = head;
                cur.next = null;
                head = cur;
            }

        }

        public void moveFromHead() {
            if (head == null) {
                System.out.println("List is empty");
                return;
            }
            if (head == tail) {
                head = tail = null;
            }else {
                head = head.last;
                head.next = null;
            }
        }

    }


    public static class Node {
        int key;
        int value;
        Node next;
        Node last;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}